package leetCode.solution;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class longestSubstringWithoutRepeatingCharacters {
	public int lengthOfLongestSubstring2(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		int maxLength = 1;
		char[] arr = s.toCharArray();
		int ends[] = new int[arr.length];
		ends[0] = 1;
		map.put(arr[0], 0);
		for (int i = 1; i < arr.length; i++) {
			ends[i] = Math.min(i - map.getOrDefault(arr[i], -1), ends[i - 1] + 1);
			map.put(arr[i], i);
			maxLength = Math.max(maxLength, ends[i]);
		}
		return maxLength;
	}
	
	// 左侧 取 Max（重复位置，前一位置最左） 的最大值
	public int lengthOfLongestSubstring3(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		char[] arr = s.toCharArray();
		int maxLength = 1;
		int preLength = 1;
		int curLength = 1;
		map.put(arr[0], 0);
		for (int i = 1; i < arr.length; i++) {
			curLength = Math.min(i - map.getOrDefault(arr[i], -1), preLength + 1);
			map.put(arr[i], i);
			maxLength = Math.max(maxLength, curLength);
			preLength = curLength;
		}
		return maxLength;
	}

	// 不断变动左侧最大值
	public int lengthOfLongestSubstring(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		int maxLength = 1;
		int l = 0, r = 0;
		for (r = 0; r < s.length(); r++) {
			if (map.containsKey(s.charAt(r))) {
				l = Math.max(map.get(s.charAt(r)) + 1, l);
			}
			maxLength = Math.max(maxLength, r - l + 1);
			map.put(s.charAt(r), r);
		}
		maxLength = Math.max(maxLength, r - l);
		return maxLength;
	}

	public int lengthOfLongestSubstring1(String s) {
		// 哈希集合，记录每个字符是否出现过
		Set<Character> occ = new HashSet<Character>();
		int n = s.length();
		// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
		int rk = -1, ans = 0;
		for (int i = 0; i < n; ++i) {
			if (i != 0) {
				// 左指针向右移动一格，移除一个字符
				occ.remove(s.charAt(i - 1));
			}
			while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
				// 不断地移动右指针
				occ.add(s.charAt(rk + 1));
				++rk;
			}
			// 第 i 到 rk 个字符是一个极长的无重复字符子串
			ans = Math.max(ans, rk - i + 1);
		}
		return ans;
	}

	public static void main(String[] args) {
		int maxSize = 20;
		for (int i = 0; i < 500000; i++) {
			StringBuffer str = new StringBuffer();
			for (int j = 0; j < maxSize; j++) {
				char x = (char) ('a' + (int) (Math.random() * 26));
				str.append(x);
			}
			if (new longestSubstringWithoutRepeatingCharacters()
					.lengthOfLongestSubstring(str.toString()) != new longestSubstringWithoutRepeatingCharacters()
							.lengthOfLongestSubstring3(str.toString())) {
				System.out.println("Oops!");
			}

		}
	}
}
